//给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 一次 或 两次 。请你找出所有出现 两次 
//的整数，并以数组形式返回。 
//
// 你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [4,3,2,7,8,2,3,1]
//输出：[2,3]
// 
//
// 示例 2： 
//
// 
//输入：nums = [1,1,2]
//输出：[1]
// 
//
// 示例 3： 
//
// 
//输入：nums = [1]
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// n == nums.length 
// 1 <= n <= 10⁵ 
// 1 <= nums[i] <= n 
// nums 中的每个元素出现 一次 或 两次 
// 
// Related Topics 数组 哈希表 👍 675 👎 0


package com.cjl.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * [P442]_数组中重复的数据
 *
 * @author cjl
 * @date 2022-11-19 21:26:52
 */
public class P442_FindAllDuplicatesInAnArray {
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P442_FindAllDuplicatesInAnArray().new Solution();
    }

    //力扣代码
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 利用 原始数据 nums进行存储
         * 因为nums[i] 数据有范围，因此可以增加N倍/2N倍；
         * 如果只扩大n倍，当nums[n-1]=n时， 遍历后，nums[n-1] =3n；
         *  且当n=1时，[1]数组遍历后也存在问题的情况，因此扩大2N倍
         *
         * @param nums
         * @return
         */
        public List<Integer> findDuplicates(int[] nums) {
            List<Integer> resList = new ArrayList<>();
            int n = nums.length;
            for (int i = 0; i < n; i++) {
                int tmp;
                if (nums[i] % n == 0) {
                    tmp = n;
                } else {
                    tmp = nums[i] % n;
                }
                //如果只扩大n倍，当nums[n-1]=n时， 遍历后，nums[n-1] =3n；
                // 且当n=1时，[1]数组遍历后也存在问题的情况
                nums[tmp - 1] += 2 * n;
            }
            for (int i = 0; i < n; i++) {
                if (nums[i] / (2 * n) == 2) {
                    resList.add(i + 1);
                }
            }
            return resList;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}